package com.samskievert.cactusboom;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.awt.Point;
import java.lang.String;

public class CBBoardGen
{
  final int[] DX = {0,-1, 0,1};
  final int[] DY = {1, 0,-1,0}; 
  ArrayList<Tile> moves;
  ArrayList<Tile> ghosts;
  ArrayList<Board> boards;
  //how many boards of each difficulty have been made?
  int[] boardCount = {0,0,0,0,0};
  
  CBBoardGen()
  {
   boards = new ArrayList<Board>();
   
   //go ahead and try to make 5 of each (though several of these will likely by unusable)
   for(int i = 0; i < 5; i++){
     makeBoard(1);
     makeBoard(2);
     makeBoard(3);
     makeBoard(4);
     makeBoard(5);
   }
  }
  
  int[] getBoard(int diff)
  {
    System.out.println("Difficulty: " + diff);
    //this will likely fill others with some rejects
    int test = 0;
    while(boardCount[diff-1] == 0){
      makeBoard(diff);  
    }
    for(int i = 0; i < boards.size(); i++){
      Board b = (Board)boards.get(i);
      if(b.difficulty == diff){
        boards.remove(i);
        boardCount[diff-1]--;
        //System.out.println("Difficulty: " + diff);
        String output = "{" + b.startup[0];
        for(int t = 1; t < 64; t++){output += "," + b.startup[t];}
        System.out.println(output + "};");  
        return b.startup;
      }  
    }
    return new int[] {0};    
  }
  
  void makeBoard(int diff){
    //need a starter piece to build off of...
    moves = new ArrayList<Tile>();
    ghosts = new ArrayList<Tile>();
    Random r = new Random();
    Tile t = new Tile(r.nextInt(7) + 1,r.nextInt(7) + 1,3,false);
    moves.add(t);  
   
    if(diff > 1){
      while(moveItOrLoseIt(diff) != 0){
      //do nothing!  moveItOrLoseIt does all the work
      }
   
    }else{
      int num = r.nextInt(8) + 8;  //start with 1 already
      for(int i = 0; i < num; i++){
        moveItOrLoseIt(1);
      }
    }
    
    //Now that a board has been created, we need to analyze it
    //to see if it actually fits the correct statistics.  I like
    //requiring some 0-spike cacti because it makes the board
    //less likely to be cleared in one click (other than the first)
    //1: 8-16 cacti, no 0's required
    //2: 20-28 cacti, at least two 0's
    //3: 32-40 cacti, at least three 0's
    //4: 44-52 cacti, at least four 0's
    int[] counts = new int[6];  //the 6th slot is used for the total count (just quicker than re-summing)
    for(int i = 0; i < 6; i++){counts[i] = 0;}
    for(int i = 0; i < moves.size(); i++){
      Tile tt = (Tile)moves.get(i);
      if(!tt.gap){
        counts[tt.value]++;
        counts[5]++;        
      }
    }
    
    //println("Total: " + counts[4] + "  (" + counts[0] + "/" + counts[1] + "/" + counts[2] + "/" + counts[3] + ")");
    //println("Analyzing difficulty...");
    
    int difficulty = 0;  //unusable 
    if(counts[5] >= 56 && counts[0] >= 5) difficulty = 5;
    else if(counts[5] >= 44 && counts[5] <= 52 && counts[0] >= 4) difficulty = 4;
    else if(counts[5] >= 32 && counts[5] <= 40 && counts[0] >= 3) difficulty = 3;
    else if(counts[5] >= 20 && counts[5] <= 28 && counts[0] >= 2) difficulty = 2;
    else if(counts[5] >=  8 && counts[5] <= 16) difficulty = 1;    
    else return;  //no use continuing on if we got a failure        
    
    /*
     *This was a pretty lazy solution...added too many spikes to the pool and made it to 
     *easy to just click on any three and have it blow up everything...
     *
    //the patterns were a bit too transparent, so I also need to throw in some Red Herrings
    int threeCount = 0;
    if(difficulty == 1) threeCount = 4;
    if(difficulty == 2) threeCount = 7;
    if(difficulty == 3) threeCount = 10;
    if(difficulty == 4) threeCount = 13;
    if(difficulty == 5) threeCount = 16;
    
    while(counts[3] < threeCount)
    {
        int nextPos = 0;
        int selection = r.nextInt(counts[1] + counts[2]);
        //int[] cand = new int[counts[1] + counts[2]];
        for(int i = 0; i < moves.size(); i++)
        {
            Tile tt = (Tile)moves.get(i);
            if(tt.value == 2 || tt.value == 1) 
            {
                if(nextPos == selection){
                    counts[tt.value]--;
                    counts[3]++;
                    tt.value = 3;
                    break;
                }else{
                    nextPos++;    
                }
            }
        }
        
    }
     */
    
    
    int[] rightOrder = new int[64];
    Arrays.fill(rightOrder,-1);
    for(int i = 0; i < moves.size(); i++)
    {
      Tile tt = (Tile)moves.get(i);
      if(tt.gap) rightOrder[tt.x + tt.y*8] = -1;
      else rightOrder[tt.x + tt.y*8] = tt.value;
    }
    //finally, add the board to the list!
    boards.add(new Board(difficulty, rightOrder));
    boardCount[difficulty-1]++;
  }//end of makeBoard
  
  //a Board is a 64-integer array where each int
  //is the number of spikes to put on the cactus
  //at that position on an 8x8 board (-1 means empty)
  class Board
  {
   int difficulty; 
   int[] startup;
   Board(int d, int[] s)
   {
    difficulty = d;
    startup = s; 
   }    
  }//end of Board
  
  //The Tile class serves a couple of functions.  With a 
  //value, a Tile represents a piece that has already been
  //placed.  Marked as a "gap," a Tile represents an piece
  //which must remain empty.  A "ghost" represents a possible
  //move, and its value (-) represents how many spikes it can
  //draw.
  class Tile
  {
    int x; int y;  //position on the grid
    int value;     //positive for a tile, negative for a ghost
    //each cactus, upon explosion, shoots spikes out in four directions
    //this boolean array records which spikes have been claimed by other
    //cacti
    boolean[] used = {false,false,false,false};  
    boolean ghost;  //am I a ghost tile?
    //if a cactus claims a spike from another cactus sepearted by a gulf,
    //the chain reaction could be broken if another tile were placed in 
    //between them...therefore such tiles become empty gaps
    boolean gap;    //do I represent a gap?
 
    //bells & whistles constructor...really only used for the first tile
    Tile(int _x, int _y, int v, boolean g){
      x = _x;
      y = _y;
      value = v;
      ghost = g;
    }
    
    //all possible expansions take place on a ghost tile, so it's easier 
    //to just pass that ghost than to recreate a new tile alltogether
    Tile(Tile ghost){
      x = ghost.x;
      y = ghost.y;
      value = Math.max(0,4 + ghost.value);
    }
 
   //if we don't give anything else, assume it's a gap
   Tile(int _x, int _y) 
   {
     x = _x;
     y = _y;
     //gaps don't get spikes to "spend"
     used= new boolean[] {true,true,true,true};
     value = 0;
     ghost = false;
     gap = true;
   }
  }//end of Tile
  
  //this would need to be modified if the board size is anything other than 8x8
  boolean inBounds(int x, int y){
    if(x < 0 || y < 0 || x > 7 || y > 7) return false;
    return true; 
  }
  
  //addTile adds a new Tile to the moves list at the specified coordinates,
  //then goes through the already placed moves and deactivates the spikes
  //that would be needed to make this cactus explode 
  void addTile(int tx, int ty){
    evaluateMove(tx,ty);
    for(int i = 0; i < ghosts.size(); i++){
      Tile t = (Tile)ghosts.get(i);
      if(t.x == tx && t.y == ty){
        Tile newGuy = new Tile(t);
        //now go through all the Tiles and turn off the ones that fed this one
        moves.add(newGuy);
        int hungry = 4 - newGuy.value;  //if I could take more than 4 spikes...I only need 4
        for(int j = 0; j < moves.size(); j++){
          Tile m = (Tile)moves.get(j);
          if(m.y > newGuy.y && m.x == newGuy.x && !m.used[2] && hungry > 0){ //same col, bigger Y
            m.used[2] = true;
            hungry--;
            fillGap(m,newGuy);
          }
          if(m.y < newGuy.y && m.x == newGuy.x && !m.used[0] && hungry > 0){ //same col, smaller Y
            m.used[0] = true;  
            hungry--;
            fillGap(m,newGuy);
          }
          if(m.x > newGuy.x && m.y == newGuy.y && !m.used[1] && hungry > 0){ //same row, bigger X
            m.used[1] = true; 
            hungry--; 
            fillGap(m,newGuy);
          }
          if(m.x < newGuy.x && m.y == newGuy.y && !m.used[3] && hungry > 0){ //same row, smaller X
            m.used[3] = true;  
            hungry--;
            fillGap(m,newGuy);
          }
      }
      doGhosts();
      break;
      }
    }
  }
  
  //The doGhosts function takes a look at every space left on the board and figures
  //out how many spikes are "pointing" at that spot.  If the first cactus were clicked
  //on first, this number represents the number of spikes that would pass through
  //that square.  If the number is 1, that means a cactus with 3 spikes is needed to 
  //continue the chain reaction.
  void doGhosts()
  {
    ghosts = new ArrayList<Tile>();
    int[][] boardState = new int[8][8];
    for(int i = 0; i < 8; i++){
      for(int j = 0; j < 8; j++){
        boardState[i][j] = 0;
      }
    }
    //adds the tiles in the order they were placed (very important)
    for(int i = 0; i < moves.size(); i++){
      Tile t = (Tile)moves.get(i);
      if(!t.ghost) boardState[t.x][t.y] = 1;
      //send points out in each unused direction
      for(int j = 0; j < 4; j++){
        if(!t.used[j]){
          int tx = t.x;
          int ty = t.y;
          while(inBounds(tx + DX[j],ty + DY[j])){ //if the next move is in bounds...
            tx += DX[j];
            ty += DY[j];
            //ignore the values of any already placed pieces
            if(boardState[tx][ty] <= 0) boardState[tx][ty]--;
          }
        }
      }
    }
  
    for(int i = 0; i < 8; i++){
      for(int j = 0; j < 8; j++){
        if(boardState[i][j] < 0) ghosts.add(new Tile(i,j,boardState[i][j],true));
      }
    }
  }
  
  //The fillGap function converts all empty spaces between two tiles into gaps
  void fillGap(Tile a, Tile b)
  {
    for (int i = 0; i < ghosts.size(); i++){
      Tile c = (Tile)ghosts.get(i);
      if(a.y == b.y){  //same row
        if(c.y == a.y && ((c.x > a.x && c.x < b.x) || (c.x < a.x && c.x > b.x))) moves.add(new Tile(c.x,c.y));  
      }
      if(a.x == b.x){  //same column
        if(c.x == a.x && ((c.y > a.y && c.y < b.y) || (c.y < a.y && c.y > b.y))) moves.add(new Tile(c.x,c.y));       
      }
    }
    doGhosts(); 
  }//end of fillGap
  
  //The gapCount fuction counts how many gaps WOULD be created if the two given tiles were
  //actually on the board.
  int gapCount(Tile a, Tile b) 
  {
    int gC = 0;
    for (int i = 0; i < ghosts.size(); i++){
      Tile c = (Tile)ghosts.get(i);
      if(a.y == b.y){
        if(c.y == a.y && ((c.x > a.x && c.x < b.x) || (c.x < a.x && c.x > b.x))) gC++;  
      }
      if(a.x == b.x){
        if(c.x == a.x && ((c.y > a.y && c.y < b.y) || (c.y < a.y && c.y > b.y))) gC++;
      }
    }
   return gC++;
  }//end of gapCount
  
  //The evaluateMove function returns how many gaps would be created (looking in every direction)
  //if a piece were to actually be placed at the specified coordinates
  int evaluateMove(int tx, int ty){
    int[] gaps = {0,0,0,0};
    for(int i = 0; i < ghosts.size(); i++){
      Tile t = (Tile)ghosts.get(i);
      if(t.x == tx && t.y == ty){
        Tile newGuy = new Tile(t);
        //go through all the Tiles and find out which ones are feeding this one
        int hungry = 4 - newGuy.value;
        for(int j = 0; j < moves.size(); j++){
          Tile m = (Tile)moves.get(j);
          if(m.y > newGuy.y && m.x == newGuy.x && !m.used[2] && hungry > 0){ //same col, bigger Y
            if(gaps[2] < gapCount(m,newGuy)) gaps[2] = gapCount(m,newGuy);
            hungry--;
          }
          if(m.y < newGuy.y && m.x == newGuy.x && !m.used[0] && hungry > 0){ //same col, smaller Y
            if(gaps[0] < gapCount(m,newGuy)) gaps[0] = gapCount(m,newGuy);
            hungry--;
          }
          if(m.x > newGuy.x && m.y == newGuy.y && !m.used[1] && hungry > 0){ //same row, bigger X
            if(gaps[1] < gapCount(m,newGuy)) gaps[1] = gapCount(m,newGuy);
            hungry--; 
          }
          if(m.x < newGuy.x && m.y == newGuy.y && !m.used[3] && hungry > 0){ //same row, smaller X
            if(gaps[3] < gapCount(m,newGuy)) gaps[3] = gapCount(m,newGuy);
            hungry--;
          }
        }
        break;
      }
    }
    int totalGaps = gaps[0] + gaps[1] + gaps[2] + gaps[3];
    return totalGaps;
  }//end of evaluateMove

  //The moveItOrLoseIt function is the bread and butter of the boardGenerator.
  //It cycles through all available ghosts (possible moves) and categorizes
  //them based on priority.  A cactus with 0 spikes (ghost value <= -4) is
  //considered best, while ones with 1,2, and 3 are considered less valuable
  //moves.  Because puzzles of difficulty 0/1/2/3/4 need a different total number
  //of cacti placed, the difficulty sets how far afield we're allowed to look
  //for the next move.  We want as many 0-spike cacti as possible, but on the
  //higher difficulty puzzles it's not worth creating a bunch of gaps to go 
  //get them.
  
  int moveItOrLoseIt(int difficulty){
    
    //make sure the ghosts are updated
    doGhosts();
    
    int threeCount = 0;
    if(difficulty == 1) threeCount = 4;
    if(difficulty == 2) threeCount = 7;
    if(difficulty == 3) threeCount = 10;
    if(difficulty == 4) threeCount = 13;
    if(difficulty == 5) threeCount = 16;
    
    int numThrees = 0;
    for(int i = 0; i < moves.size(); i++){
        Tile tt = moves.get(i);
        if(tt.value == 3) numThrees++;
    }
    
    //How many gaps are allowed when deciding when to place a new piece?
    //The higher the numbers, the faster the board gets filled with gaps.
    int[] gA = {1,0,0,0};
    if(difficulty == 4) gA = new int[] {2,1,0,0};
    if(difficulty == 3) gA = new int[] {4,3,2,1};
    if(difficulty <= 2) gA = new int[] {8,8,8,8};

    ArrayList<Point> greats = new ArrayList<Point>();  //-4 or lower
    ArrayList<Point> okays = new ArrayList<Point>();   //-3
    ArrayList<Point> decents = new ArrayList<Point>(); //-2
    ArrayList<Point> sads = new ArrayList<Point>();    //-1
    
    //Go through all the ghosts and sort them into 
    //the above ArrayLists
    for(int i = 0; i < ghosts.size(); i++)
    {
      Tile t = (Tile)ghosts.get(i);
      if(t.value <= -4) greats.add(new Point(t.x,t.y));
      if(t.value == -3) okays.add(new Point(t.x,t.y));
      if(t.value == -2) decents.add(new Point(t.x,t.y));
      if(t.value == -1) sads.add(new Point(t.x,t.y));     
    }   
    
    Random rand = new Random();

    if(greats.size() > 0){  //if we have any "great" candidates
      int numTries = 0;
      while(numTries < 20){ //cycle through a few times
        numTries++;
        int r = rand.nextInt(greats.size());
        Point p = (Point)greats.get(r);
        //only allow as many gaps as are set by this difficulty rating
        if(evaluateMove(p.x,p.y) <= gA[0]){
          addTile(p.x,p.y);
          if(numThrees < threeCount) addThree(gA[3]);          
          return -4;     
        }
      }  
    }  
   
    if(okays.size() > 0){
      int numTries = 0;
      while(numTries < 20){
        numTries++;
        int r = rand.nextInt(okays.size());
        Point p = (Point)okays.get(r);
        if(evaluateMove(p.x,p.y) <= gA[1]){
          addTile(p.x,p.y);
          if(numThrees < threeCount) addThree(gA[3]);
          return -3;
        }
      }
    }

    if(decents.size() > 0){
      int numTries = 0;
      while(numTries < 30){
        numTries++;
        int r = rand.nextInt(decents.size());
        Point p = (Point)decents.get(r);
        if(evaluateMove(p.x,p.y) <= gA[2]){
          addTile(p.x,p.y);
          if(numThrees < threeCount) addThree(gA[3]);          
          return -2;     
        }
      }     
    }
   
    if(sads.size() > 0){
      int numTries = 0;
      while(numTries < 50){
        numTries++;
        int r = rand.nextInt(sads.size());
        Point p = (Point)sads.get(r);
        if(evaluateMove(p.x,p.y) <= gA[3]){
          addTile(p.x,p.y);
          return -1;     
        }
      }
    }
    //return 0 if there are no moves left
    return 0;
  }
  
  
  //this is essentially a limited version of MoveItOrLoseIt(), only it actually
  //seeks out any threes and chooses among the closest.  This seeds the board with
  //more possible "starting" clicks that won't neccessarily clear the board.
  void addThree(int roamDist){
    doGhosts();
    Random rand = new Random();
    ArrayList<Point> sads = new ArrayList<Point>();    //-1
    
    //Grab all the bad moves
    for(int i = 0; i < ghosts.size(); i++)
    {
      Tile t = (Tile)ghosts.get(i);
      if(t.value == -1) sads.add(new Point(t.x,t.y));     
    }
    
    if(sads.size() > 0){
      int numTries = 0;
      while(numTries < 50){
        numTries++;
        int r = rand.nextInt(sads.size());
        Point p = (Point)sads.get(r);
        if(evaluateMove(p.x,p.y) == 0){
          addTile(p.x,p.y);
          return;
        }
      }
    }
      
  }  
  
}
